package com.zhj.leetcode;

/**
 * 力扣206 反转链表
 * @author zhj
 */
public class Test206 {

    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(6, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6)))))));
        ListNode listNode = reverseListDG(head);
        System.out.println(listNode);
    }

    private static ListNode reverseList(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        while (head != null && head.next != null) {
            // 临时链表的下一个
            ListNode dNext = dummy.next;
            // 原链表的下一个
            ListNode hNext = head.next;
            // 零时链表的下一个指向原链表的下一个
            dummy.next = hNext;
            // 原链表的下一个指向原链表的下一个的下一个
            head.next = hNext.next;
            // 原链表的下一个的下一个指向零时链表的下一个
            hNext.next = dNext;
        }
        return dummy.next;
    }

    private static ListNode reverseListDG(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = reverseListDG(head.next);
        head.next.next = head;
        head.next = null;
        return dummy;
    }
}
